/*
 rope - The C++ string algorithm library

 Copyright (C) 2008 Woojong Koh (jstrane@gmail.com)

 This program is free software; you can redistribute it and/or modify
 it under the terms of the GNU General Public License as published by
 the Free Software Foundation; either version 2 of the License, or
 (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License along
 with this program; if not, write to the Free Software Foundation, Inc.,
 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.

 Project page : http://code.google.com/p/rope 
*/
#ifndef AHO_CORASICK_IMPL_H
#define AHO_CORASICK_IMPL_H

#include <iostream>
#include <boost/date_time/posix_time/posix_time.hpp>

template<class T>
void aho_corasick<T>::build() throw(std::length_error)
{
	g_.clear();
	goto_.clear();
	failure_.clear();

	boost::posix_time::ptime t1(boost::posix_time::microsec_clock::local_time());

	pattern_char_ = get(edge_name, g_);
	out_ = get(vertex_name, g_);

	// construct a trie
	root_ = add_vertex(g_);

	for (pattern_cont_iter pat_it = patterns_.begin(); pat_it != patterns_.end(); ++pat_it)
	{
		Vertex v = root_;
		const string_t& pattern = *pat_it;

		for (str_cont_iter it = pattern.begin(); it != pattern.end(); ++it)
		{
			Vertex t = goto_func(v, *it);

			if (t == null_vertex_ || t == root_) // dead end :(
			{
				Vertex new_v = add_vertex(g_);

				Edge e;
				bool inserted;
				tie(e, inserted) = add_edge(v, new_v, g_);

				if (__builtin_expect(inserted, 1))
				{
					pattern_char_[e] = *it; 
					set_goto_func(v, *it, new_v);
					if (v == root_)
						set_fail_func(new_v, root_);
				}
				else
					throw std::length_error("exception: add edge failed.");
				v = new_v;
			}
			else
				v = t;
		}

		out_list_t& out_v = out_[v];
		if (out_v.empty())
			out_v.push_back(pattern);
	}
	boost::posix_time::ptime t2(boost::posix_time::microsec_clock::local_time());

	// build a fail/out function
	ac_constructor vis(*this);
	breadth_first_search(g_, root_, visitor(vis));

	boost::posix_time::ptime t3(boost::posix_time::microsec_clock::local_time());

	std::cout << "add vertex : " << t2 - t1 << std::endl;
	std::cout << "build fail/out : " << t3 - t2 << std::endl;
	std::cout << "overall : " << t3 - t1 << std::endl;
}

template<class T>
typename aho_corasick<T>::Vertex aho_corasick<T>::goto_func(Vertex q, char_t a) const
{
	typename goto_t::const_iterator it = goto_.find(std::make_pair(q, a));

	if (it != goto_.end()) return it->second;
	else if (q == root_) return root_;
	return null_vertex_;
}

template<class T>
template<class InputIterator>
typename aho_corasick<T>::result_list_t aho_corasick<T>::search(InputIterator beg, InputIterator end) const
{
	boost::posix_time::ptime t1(boost::posix_time::microsec_clock::local_time());

	result_list_t result;
	Vertex q = root_;
	for (InputIterator it = beg; it != end; ++it)
	{
		while (goto_func(q, *it) == null_vertex_)
		{
			q = fail_func(q);
		}
		q = goto_func(q, *it);

		const out_list_t& out_list = out_[q];
		if (!out_list.empty())
			result.insert(result.end(), std::make_pair((it + 1) - beg, out_list));
	}

	boost::posix_time::ptime t2(boost::posix_time::microsec_clock::local_time());
	std::cout << "search time : " << t2 - t1 << std::endl;

	if (!result.empty())
	{
		for (result_cont_iter it = result.begin(); it != result.end(); ++it)
		{
			std::cout << it->first << " ";
			std::copy(it->second.begin(), it->second.end(), std::ostream_iterator<string_t>(std::cout, " "));
			std::cout << std::endl;
		}
	}

	return result;
}

#include <algorithm>

template<class T>
template<class InputIterator1, class InputIterator2, class OuputIterator>
OuputIterator aho_corasick<T>::replace(InputIterator1 beg, InputIterator1 end, InputIterator2 rep_beg, InputIterator2 rep_end,
									   OuputIterator result, const result_list_t& searched) const
{
	if (!searched.empty())
	{
		boost::posix_time::ptime t1(boost::posix_time::microsec_clock::local_time());

		InputIterator1 prev_end = beg;
		for (result_cont_iter it = searched.begin(); it != searched.end(); ++it)
		{
			const string_t& matched = it->second.back();

			InputIterator1 pat_end = beg + it->first;
			InputIterator1 pat_beg = pat_end - matched.length();

			if (prev_end > pat_beg) continue;

			result = std::copy(prev_end, pat_beg, result);
			result = std::copy(rep_beg, rep_end, result);

			prev_end = pat_end;
		}
		result = std::copy(prev_end, end, result);

		boost::posix_time::ptime t2(boost::posix_time::microsec_clock::local_time());
		std::cout << "replace time : " << t2 - t1 << std::endl;
	}
	return result;
}

#include <boost/algorithm/string.hpp>

template<class T>
T aho_corasick<T>::replace_bf(string_t text) const
{
	boost::posix_time::ptime t1(boost::posix_time::microsec_clock::local_time());

	for (pattern_cont_iter it = patterns_.begin(); it != patterns_.end(); ++it)
	{
		boost::replace_all(text, *it, "[CENSORED]");
	}

	boost::posix_time::ptime t2(boost::posix_time::microsec_clock::local_time());
	std::cout << "search and replace(brute force) time : " << t2 - t1 << std::endl;

	return text;
}

#endif
